/**
 * @author 雷明浩
 * @date 2025/6/3 10:59
 */
public class ReverseBetween {
    // newcoder 链表内指定区反转
    // https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=23286&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode leftHead = head;
        ListNode leftTail = null;
        ListNode midHead = null;
        ListNode midTail = null;
        ListNode rightHead = null;
        ListNode cur = head;
        int index = 1;
        while (cur != null) {
            if (index == m-1) {
                leftTail = cur;
            }else if (index == m) {
                if (index == n) {
                    return head;
                }
                midHead = cur;
            }else if (index == n) {
                midTail = cur;
            }else if (index == n+1) {
                rightHead = cur;
                break;
            }
            cur = cur.next;
            index++;
        }
        midTail.next = null;
        ListNode newMidHead = reverseList(midHead);
        midHead.next = rightHead;
        if (leftTail != null) {
            leftTail.next = newMidHead;
            return leftHead;
        }else {
            return newMidHead;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);
        ReverseBetween reverseBetween = new ReverseBetween();
        head = reverseBetween.reverseBetween(head, 1, 2);
    }
}